# scrypt

## 개요
**scrypt**는 2009년 Tarsnap의 설립자인 Colin Percival에 의해 설계된 암호화 해시 함수이자 키 유도 함수(KDF, Key Derivation Function)입니다. 

scrypt는 기존의 `pbkdf2`나 `bcrypt`와 같은 알고리즘들이 CPU 연산량만을 늘려 공격을 방어하려 했던 한계를 극복하기 위해 설계되었습니다. 특히 ASIC(주문형 반도체)이나 FPGA와 같은 전용 하드웨어를 이용한 대규모 병렬 무차별 대입 공격(Brute-force attack)을 효과적으로 방어하기 위해, 연산 과정에서 상당한 양의 메모리를 요구하는 **'메모리 하드닝(Memory-hardening)'** 기법을 도입한 것이 핵심입니다.

## 작동 원리

### 파라미터 설정
scrypt는 보안 강도를 세밀하게 조정하기 위해 다음과 같은 세 가지 주요 파라미터를 사용합니다.

*   **$N$ (CPU/메모리 비용 파라미터):** 전체적인 연산 비용과 메모리 사용량을 결정하는 값입니다. $N$이 커질수록 더 많은 메모리와 CPU 시간이 소요되며, 공격자가 하드웨어를 통해 공격할 때 필요한 비용이 기하급수적으로 증가합니다. (반드시 2의 거듭제곱 값이어야 함)
*   **$r$ (블록 크기 파라미터):** 메모리 내에서 한 번에 처리하는 블록의 크기를 결정합니다. 이는 메모리 대역폭과 효율성에 영향을 줍니다.
*   **$p$ (병렬화 파라미터):** 연산을 병렬로 처리할 수 있는 정도를 결정합니다. $p$를 높이면 다중 코어 CPU를 사용하여 더 빠르게 해시를 생성할 수 있지만, 공격자 역시 동일한 병렬성을 이용할 수 있습니다.

### 메모리 하드닝
scrypt의 핵심은 대량의 데이터를 메모리에 저장하고, 이를 무작위 순서로 읽고 쓰는 과정을 반복하는 것입니다. 

1. 먼저 입력값과 솔트(Salt)를 이용해 임시 데이터를 생성하여 큰 메모리 배열에 저장합니다.
2. 이후 저장된 데이터의 무작위 인덱스를 참조하여 계속해서 값을 섞는 과정을 거칩니다.
3. 이 과정에서 공격자가 메모리 사용량을 줄이려고 시도하면(Time-Memory Trade-off), 연산 시간이 폭발적으로 증가하게 되어 공격 효율이 급격히 떨어지게 됩니다.

## 타 알고리즘과의 비교

| 구분 | PBKDF2 | bcrypt | scrypt |
| :--- | :--- | :--- | :--- |
| **주요 자원 소모** | CPU (연산 반복) | CPU (연산 반복) | CPU + **메모리** |
| **하드웨어 공격 방어** | 낮음 (GPU/ASIC에 취약) | 보통 (FPGA에 일부 취약) | 높음 (ASIC 설계 비용 증가) |
| **설정 유연성** | 반복 횟수 설정 가능 | 비용(Cost) 설정 가능 | $N, r, p$ 세부 설정 가능 |
| **주요 특징** | 표준화된 범용 KDF | 패스워드 해싱의 표준 | 메모리 집약적 설계 |

## 보안성 및 한계
scrypt는 하드웨어 가속 공격에 대해 매우 강력한 저항력을 가지지만, 다음과 같은 한계가 존재합니다.

*   **자원 소모:** 서버 측에서 많은 사용자의 인증을 동시에 처리해야 할 경우, 높은 메모리 요구량으로 인해 서버 자원이 빠르게 고갈될 수 있습니다.
*   **DoS 공격 위험:** 공격자가 매우 높은 파라미터 값을 요청하는 요청을 대량으로 보낼 경우, 서버의 메모리를 고갈시켜 서비스 거부(DoS) 상태로 만들 위험이 있습니다. 따라서 서버 설정 시 적절한 상한선을 두어야 합니다.

## 사용 사례 및 구현

### 사용 사례
*   **암호화폐:** 라이트코인(Litecoin) 등 초기 여러 알트코인들이 채굴 알고리즘으로 채택하여 ASIC 채굴기의 독점을 막으려 했습니다.
*   **패스워드 저장:** 높은 보안 수준이 요구되는 시스템의 사용자 비밀번호 저장 및 검증.
*   **디스크 암호화:** 마스터 키로부터 암호화 키를 유도하는 과정.

### 구현 예제 (Python)
Python의 `hashlib` 라이브러리를 사용하여 scrypt를 구현하는 간단한 예제입니다.

```python
import hashlib
import os

# 파라미터 설정
password = b"my_secure_password"
salt = os.urandom(16)  # 무작위 솔트 생성
n = 16384              # CPU/메모리 비용
r = 8                  # 블록 크기
p = 1                  # 병렬화 파라미터

# 키 유도 (Key Derivation)
key = hashlib.scrypt(password, salt=salt, n=n, r=r, p=p, dklen=64)

print(f"Derived Key: {key.hex()}")
```

## 참고 문헌/관련 문서
*   RFC 7914: scrypt Key Derivation Function
*   Colin Percival, "scrypt: Password-Based Key Derivation with Sequential Memory-Hard Functions"